Search results for " pre-necklaces"

showing 2 items of 2 documents

On prefix normal words and prefix normal forms

2016

A $1$-prefix normal word is a binary word with the property that no factor has more $1$s than the prefix of the same length; a $0$-prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching, where the aim is to decide whether a word has a factor with a given number of $1$s and $0$s (a given Parikh vector). Each binary word has an associated set of Parikh vectors of the factors of the word. Using prefix normal words, we provide a characterization of the equivalence class of binary words having the same set of Parikh vectors of their factors. We prove that the language of prefix normal words is not context-free and is strictly contai…

FOS: Computer and information sciencesPrefix codePrefix normal wordPre-necklaceDiscrete Mathematics (cs.DM)General Computer ScienceFormal Languages and Automata Theory (cs.FL)Binary numberComputer Science - Formal Languages and Automata TheoryContext (language use)Binary languageLyndon words0102 computer and information sciences02 engineering and technologyPrefix grammarprefix normal formsKraft's inequalityCharacterization (mathematics)Lyndon word01 natural sciencesPrefix normal formenumerationTheoretical Computer ScienceFOS: Mathematics0202 electrical engineering electronic engineering information engineeringMathematics - CombinatoricsMathematicsDiscrete mathematicsprefix normal words prefix normal forms binary languages binary jumbled pattern matching pre-necklaces Lyndon words enumerationbinary jumbled pattern matchingSettore INF/01 - InformaticaComputer Science (all)pre-necklacesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)prefix normal wordsPrefix010201 computation theory & mathematics020201 artificial intelligence & image processingCombinatorics (math.CO)binary languagesComputer Science::Formal Languages and Automata TheoryWord (group theory)Computer Science - Discrete MathematicsTheoretical Computer Science
researchProduct

On Prefix Normal Words

2011

We present a new class of binary words: the prefix normal words. They are defined by the property that for any given length $k$, no factor of length $k$ has more $a$'s than the prefix of the same length. These words arise in the context of indexing for jumbled pattern matching (a.k.a. permutation matching or Parikh vector matching), where the aim is to decide whether a string has a factor with a given multiplicity of characters, i.e., with a given Parikh vector. Using prefix normal words, we give the first non-trivial characterization of binary words having the same set of Parikh vectors of factors. We prove that the language of prefix normal words is not context-free and is strictly contai…

permutation matchingcontext-free languagesSearch engine indexingpre-necklacesBinary numberParikh vectorsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Lyndon wordsnon- standard pattern matchingLyndon wordsCombinatoricsPrefixjumbled pattern matchingPattern matchingParikh vectors; pre-necklaces; Lyndon words; context-free languages; jumbled pattern matching; permutation matching; non- standard pattern matching; indexingComputer Science::Formal Languages and Automata TheoryParikh vectors pre-necklaces Lyndon words context-free languages jumbled pattern matching permutation matching non-standard pattern matching indexingMathematicsindexing
researchProduct